﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>

using namespace std;
//给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。
// 请在不改变其结构的情况下，恢复这棵树 。
//
//
//
//示例 1：
//
//
//输入：root = [1, 3, null, null, 2]
//输出：[3, 1, null, null, 2]
//解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。




  struct TreeNode {
      int val;
      struct TreeNode *left;
      struct TreeNode *right;
  };
 
int len, max_size;

void inorder(struct TreeNode* root, int** nums) {
    if (root == NULL) {
        return;
    }
    inorder(root->left, nums);
    (*nums)[len++] = root->val;
    if (len == max_size) {
        max_size <<= 1;
        (*nums) = (int*)realloc((*nums), sizeof(int) * max_size);
    }
    inorder(root->right, nums);
}

int* findTwoSwapped(int* nums) {
    int index1 = -1, index2 = -1;
    for (int i = 0; i < len - 1; ++i) {
        if (nums[i + 1] < nums[i]) {
            index2 = i + 1;
            if (index1 == -1) {
                index1 = i;
            }
            else {
                break;
            }
        }
    }
    int x = nums[index1], y = nums[index2];
    int* ret = (int*)malloc(sizeof(int) * 2);
    ret[0] = x, ret[1] = y;
    return ret;
}

void recover(struct TreeNode* r, int count, int x, int y) {
    if (r != NULL) {
        if (r->val == x || r->val == y) {
            r->val = r->val == x ? y : x;
            if (--count == 0) {
                return;
            }
        }
        recover(r->left, count, x, y);
        recover(r->right, count, x, y);
    }
}

void recoverTree(struct TreeNode* root) {
    len = 0, max_size = 1;
    int* nums = (int*)malloc(sizeof(int));
    inorder(root, &nums);
    int* swapped = findTwoSwapped(nums);
    recover(root, 2, swapped[0], swapped[1]);
}
